#include <bits/stdc++.h>

using namespace std;

// 砍竹子II
// 现需要将一根长为正整数bamboo_len的竹子砍为若干段
// 每段长度均为正整数
// 请返回每段竹子长度的最大乘积是多少
// 答案需要对1000000007取模
// 测试链接 : https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/

class Solution 
{
public:
    // 快速幂测试链接 ：https://leetcode.cn/problems/powx-n/
	// 快速幂，求余数
	// 求x的n次方，最终得到的结果 % mod
    long power(long x, int n, int mod)
    {
        long ans = 1;
        while(n > 0)
        {
            if(n & 1) ans = ans * x % mod;
            n >>= 1;
            x = x * x % mod;
        }
        return ans;
    }

    int cuttingBamboo(int n) 
    {
        if(n == 2) return 1; // 1 * 1
        if(n == 3) return 2; // 1 * 2
        int mod = 1e9 + 7;
		// n = 4 ->  2 * 2
		// n = 5 ->  3 * 2
		// n = 6 ->  3 * 3
		// n = 7 ->  3 * 2 * 2
		// n = 8 ->  3 * 3 * 2
		// n = 9 ->  3 * 3 * 3
		// n = 10 -> 3 * 3 * 2 * 2
		// n = 11 -> 3 * 3 * 3 * 2
        int tail = n % 3 == 0 ? 1 : (n % 3 == 1 ? 4 : 2);
        int k = (tail == 1 ? n : (n - tail)) / 3;
        return power(3, k, mod) * tail % mod; 
    }
};


// 整数拆分：https://leetcode.cn/problems/integer-break/

class Solution 
{
public:
    long power(long x, int n)
    {
        long ans = 1;
        while(n > 0)
        {
            if(n & 1) ans *= x;
            n >>= 1;
            x *= x;
        }
        return ans;
    }

    // 贪心解
    int integerBreak1(int n) 
    {
        if(n == 2) return 1;
        if(n == 3) return 2;
        int rest = n % 3 == 0 ? n : (n % 3 == 1 ? (n - 4) : (n - 2));
		int last = n % 3 == 0 ? 1 : (n % 3 == 1 ? 4 : 2);
        return power(3, rest / 3) * last;
    }

    // 动态规划解
    int integerBreak2(int n) 
    {
        int dp[n + 1];
        memset(dp, 0, sizeof dp);
        dp[2] = 1;
        for(int i = 3; i <= n; ++i)
        {
            for(int j = 1; j < i; ++j)
            {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};